package com.lyz.dataStructure.JianZhiOffer.Tree;

/*
根据前序遍历和中序遍历重建二叉树
 */

public class Solution {

    static boolean valid=true;
    public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
        return root;
    }
    //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
    private static TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {

        if(startPre>endPre||startIn>endIn)
            return null;
        TreeNode root=new TreeNode(pre[startPre]);

        for(int i=startIn;i<=endIn;i++)
            if(in[i]==pre[startPre]){
                root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
                root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
                break;
            }

        return root;
    }

    private static void display(TreeNode root) {
        // TODO Auto-generated method stub
        if (root!=null) {
            display(root.left);
            display(root.right);
            System.out.print(root.val+" ");
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,2,4,7,3,5,6,8};
        int[] arr1 = {4,7,2,1,5,3,8,6};
        TreeNode node =reConstructBinaryTree(arr,arr1);
        if (valid) {
            display (node);
        }else {
            System.out.println("invalid input");
        }
    }
}
